﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

template<class K>

struct BSTNode
{
	K _key;//节点值
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{

	}

};


template<class K>
class BTTree
{
	typedef BSTNode<K> Node;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;//不应许处插入相同的值

			}
		}
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

	bool find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
			return false;
		}
	}
	//bool erase(const& K key)
	//{
	//	Node* parent = __nullptr;
	//	Node* cur = _root;
	//	while (cur)
	//	{
	//		if (key > cur->_key)
	//		{
	//			parent = cur;//要记录当前节点的父节点
	//			cur = cur->_right;
	//		}
	//		else if (key < cur->_key)
	//		{
	//			parent = cur;
	//			cur = cur->_left;
	//		}
	//		else
	//		{
	//			if (cur->_left == nullptr)
	//			{
	//				if (parent == nullptr)
	//				{
	//					_root = cur->_right;
	//				}
	//				else
	//				{
	//					if (parent->_left == cur)
	//						parent->_left = cur->_right;
	//					else
	//						parent->_right = cur->_right;
	//				}
	//				delete cur;
	//				return true;
	//			}
	//			else if (cur->_right==nullptr)
	//			{
	//				if (parent == nullptr)
	//				{
	//					_root = cur->_left;
	//				}
	//				else
	//				{
	//					if (parent->_left == cur)
	//					{
	//						parent->_left = cur->_left;

	//					}
	//					else
	//					{
	//						parent->_right = cur->_left;
	//					}
	//					delete cur;
	//					return true;
	//				}
	//			else
	//			{
	//				Node* rightMinP = cur;
	//				Node* rightMin = cur->_right;
	//				while (rightMin->_left)
	//				{
	//					rightMinP = rightMin;
	//					rightMin = rightMin->_left;
	//				}
	//				cur->_key = rightMin->_key;
	//				if (rightMinP->_left == rightMin)
	//					rightMinP->_left = rightMin->_right;
	//				else
	//					rightMinP->_right = rightMin->_right;
	//				delete rightMin;
	//				return true;
	//			}
	//			}
	//		}
	//	}
	//	return false;
	//}



	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		//从根节点开始查找
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//cur->_key == key
			{
				//左右至少有一个为空的情况，直接改变指向
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					delete cur;
					return true;
				}
				else {
					//两个子树都有孩子的情况，用右子树最小或左子树最大来替换
					// ⼀定要把cur给rightMinP，否会报错。

					//注意右子树的第一个值就是最小值的情况
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)//找出最左边的，就是右子树最小的
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}
					cur->_key = rightMin->_key;//把右子树中最小值替换到cur->_key
					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else//右子树的第一个值就是最小值的情况
						rightMinP->_right = rightMin->_right;
					delete rightMin;

					return true;
				}
			}
		}
		return false;
	}



private:
	Node* _root = nullptr;
};


int main()
{




	return 0;
}